/**
 * 编辑距离
 * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：插入/删除/替换一个字符
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
ros
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
 */

/**
 * dp[i][j] word1[i-1]和word2[j-1] 最近编辑距离为dp[i][j]
 * 1. word1[i-1]==word2[j-1] 不操作
 * dp[i][j] = dp[i-1][j-1];
 * 2. word1[i-1]!==word2[j-1]
 * 2-1 插入 dp[i][j] = dp[i][j-1] + 1    word1长度不够吗需要j回退记录 
 * 2-2 删除 dp[i][j] = dp[i-1][j] + 1    word1超长 需要i回退记录
 * 2-3 替换 dp[i][j] = dp[i-1][j-1]+1    ij当前元素不用再操作
 */
var minDistance = function(word1, word2) {
  const [m,n] = [word1.length, word2.length];
  const dp = Array(m+1).fill().map(() => Array(n+1).fill(0));
  for(let i=0;i<=m;i++) {
    dp[i][0] = i;
  }
  for(let j=0;j<=n;j++) {
    dp[0][j]=j
  }
  for(let i=1;i<=m;i++) {
    for(let j=1;j<=n;j++) {
      if(word1[i-1]==word2[j-1]) {
        dp[i][j] = dp[i-1][j-1];
      }else {
        dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
      }
    }
  }
  return dp[m][n];
};
const word1 = "horse", word2 = "ros";
console.log('编辑距离', minDistance(word1, word2)) //3;